class Solution:
    def subsetsWithDup(self, nums):
        self.res = [[]]
        for i in range(len(nums)+1):
            self.add_item([], nums, i)
        return self.res

    def add_item(self, mid_res, mid_list, k):
        if k == 1:
            for num in mid_list:
                mid = mid_res[:]
                mid.append(num)
                mid.sort()
                if mid not in self.res:
                    self.res.append(mid)
            return
        mid2 = mid_list[:]
        for num in mid_list:
            mid = mid_res[:]
            mid.append(num)
            mid2.remove(num)
            self.add_item(mid, mid2, k - 1)

a = Solution()
print(a.subsets([1, 1, 2, 2]))
print(a.subsets([1, 2, 3, 5]))
print(a.subsets([1]))
print(a.subsets([]))